//顺序表实现
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0

typedef struct
{
    int *data;
    int length;
}Sqlist;

void InitList(Sqlist *L);
void DestroyList(Sqlist *L);
void ListEmpty(Sqlist *L);
void DispList(Sqlist *L);
void GetLength(Sqlist *L);
void GetElem(Sqlist *L,int n);
void LocateElem(Sqlist *L,int e);
void ListInsert(Sqlist *L,int i,int e);
int ListDeleteAsIndex(Sqlist *L,int i);
int ListDeleteAsElem(Sqlist *L,int e);
int ListDeleteAsrepeat(Sqlist *L);

int main()
{
    int type,mode,temp,pos;
    Sqlist L;
    L.length=0;
    //函数声明

    printf("-------------------------功能菜单-------------------------\n");
    printf("【0】退出  【1】初始化  【2】打印  【3】判空  【4】求长度\n");
    printf("【5】按元素序号查找  【6】按元素值查找   【7】插入\n");
    printf("【8】按元素序号删除  【9】按元素值删除  【10】删除重复值\n");
    printf("【11】销毁  ***  毁灭吧万恶的顺序表   再也不想见到你了  ***\n"); 
    printf("---------------------------------------------------------\n");
    printf("请输入你想要的功能：");
    scanf("%d",&type);
    mode=0;          //初次使用
    while(type!=EOF)
    {
        if(mode!=0)
        {
            printf("请输入你想要的功能：");
            scanf("%d",&type);
        }
        mode=1;         //再次使用
        switch(type)
        {
            case 0:
            {
                exit(0);
                break;
            }
            case 1:
            {
                InitList(&L);
                break;
            }
            case 2:
            {
                DispList(&L);
                break;
            }
            case 3:
            {
                ListEmpty(&L);
                break;
            }
            case 4:
            {
                GetLength(&L);
                break;
            }
            case 5:
            {
                printf("请输入需要查找的元素下标：");
                scanf("%d",&pos);
                GetElem(&L,pos);
                break;
            }
            case 6:
            {
                printf("请输入需要查找的元素的值：");
                scanf("%d",&temp);
                LocateElem(&L,temp);
                break;
            }
            case 7:
            {
                printf("请输入需要插入的元素下标：");
                scanf("%d",&pos);
                printf("请输入需要插入的元素的值：");
                scanf("%d",&temp);
                ListInsert(&L,pos,temp);
                break;
            }
            case 8:
            {
                printf("请输入需要删除的元素下标：");
                scanf("%d",&pos);
                ListDeleteAsIndex(&L,pos);
                break;
            }
            case 9:
            {
                printf("请输入需要删除的元素的值：");
                scanf("%d",&temp);
                ListDeleteAsElem(&L,temp);
                break;
            }
            case 10:
            {
                ListDeleteAsrepeat(&L);
                break;
            }
            case 11:
            {
                DestroyList(&L);
                break;
            }
            default:
                break;
        }
    }
}

void InitList(Sqlist *L)
{
    L->data=(int*)malloc(MAXSIZE*sizeof(int));
    int temp,count=0;
    while(1)
    {
        scanf("%d",&temp);
        if(temp==-1)  break;
        L->data[count]=temp;
        count++;
    }
    L->length=count;
    printf("初始化成功\n");
}

void DestroyList(Sqlist *L)
{
    L->length=0;          //若是清空则只执行这一步
    free(L);
    printf("销毁成功\n");
}

void ListEmpty(Sqlist *L)
{
    if(L->length==0)  printf("顺序表为空\n");
    else  printf("顺序表不为空\n");
}

void DispList(Sqlist *L)
{
    printf("输出结果：");
    for(int i=0;i<L->length;i++)
    {
        printf("%d ",L->data[i]);
    }
    printf("\n");
}

void GetLength(Sqlist *L)
{
    printf("顺序表长度：%d\n",L->length);
}


void GetElem(Sqlist *L,int n)
{
    printf("%d下表对应元素的值：%d\n",n,L->data[n-1]);    
}

void LocateElem(Sqlist *L,int e)
{
    int mode=0;
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i]==e)
        {
            mode=1;
            printf("元素%d值的下标位置%d\n",e,i);
        }
    }
    if(mode==0)  printf("没有在列表中找到%d\n",e);
}

void ListInsert(Sqlist *L,int j,int e)
{
    if(j<1||j>L->length+1)  printf("位置错误\n");
    for(int i=L->length-1;i>=j;i--)
    {
        L->data[i+1]=L->data[i];
    }
    L->data[j]=e;
    L->length++;
    printf("插入完成\n");
}

int ListDeleteAsIndex(Sqlist *L,int i)    
{
    if (i<1||i>L->length)  return FALSE;
    for(int j=i+1;j<L->length;j++)
    {
        L->data[j-1]=L->data[j];
    }
    L->length--;
    printf("成功删除下标在%d的元素\n",i);
    return TRUE;
}

int ListDeleteAsElem(Sqlist *L,int e)    
{
    int i,mode=0;
    for(i=0;i<L->length;i++)
    {
        if(L->data[i]==e)
        {
            ListDeleteAsIndex(L,i);   //这个地方为什么不加取地址符号？
            mode=1;
        }
    }
    if(mode==0)
    {
        printf("找不到值为%d的元素\n",e);
        return FALSE;
    }
    printf("成功删除所有值为%d的元素\n",e);
    return TRUE;
}

int ListDeleteAsrepeat(Sqlist *L)
{
    for(int i=0;i<L->length;i++)
    {
        for(int j=i+1;j<L->length;j++)
        {
            if(L->data[j]==L->data[i])
            {
                ListDeleteAsIndex(L,j);
                j--;                      //对j进行回溯，防止出现连续多个重复值
            }
        }
    }
    printf("成功删除所有重复的值\n");
    return TRUE;
}

/*   失败的快速排序代码
void mix(Sqlist *L,int low,int middle,int high)
{
	int auxiliary[100];           //新建一个临时的辅助数组 
	int i=low,j=middle+1,k=0;
	while(i<=middle&&j<=high)
	{
		if(L->data[i]<=L->data[j])    auxiliary[k++]=L->data[i++];    //每次循环提取array两个部分([low:middle]和[middle+1:high])剩余元素最小值
		else                          auxiliary[k++]=L->data[j++]; 
	}
	while(i<=middle)   auxiliary[k++]=L->data[i++];   //将array前半部分[low:middle]的剩余元素添加后辅助数组后面 
	while(j<=high)     auxiliary[k++]=L->data[j++];   //将array后半部分[middle+1:high]的剩余元素添加到辅助数组后面
    //其实上面两个过程不可能同时发生（本函数第一次while循环决定的）
	for(i=low,k=0;i<=high;i++)
	{
		L->data[i]=auxiliary[k++];
	}
}

void SqlistSort(Sqlist *L)
{
	int middle,low=0,high=L->length-1;
	if(low==high)  return 0;
	else
	{
		middle=(low+high)/2;
		SqlistSort(L,low,middle);      //将array[low:middle]进行递归拆分成单个元素再合并回有序的array[low:middle] 
		SqlistSort(L,middle+1,high);   //将array[middle+1:high]进行递归拆分成单个元素再合并回有序的array[middle+1:high] 
		mix(L,low,middle,high);  //将array[low:middle]和[middle+1:high]合并成有序的[low:high] 
	}
}
*/